﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0142_RandomizedSet : IAlgorithm
    {
        // 常数时间插入、删除和获取随机元素

        // 实现RandomizedSet 类：
        //  RandomizedSet() 初始化 RandomizedSet 对象
        //  bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
        //  bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
        //  int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
        // 你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

        // 提示：
        //  -2^31 <= val <= 2^31 - 1
        //  最多调用 insert、remove 和 getRandom 函数 2 * 10^5 次
        //  在调用 getRandom 方法时，数据结构中 至少存在一个 元素。


        public void Test()
        {
            // 算法参数定义
            var rs = new RandomizedSet();
            // 算法执行与打印
            Console.WriteLine(rs.Insert(1));
            Console.WriteLine(rs.Remove(2));
            Console.WriteLine(rs.Insert(2));
            Console.WriteLine(rs.GetRandom());
            Console.WriteLine(rs.Remove(1));
            Console.WriteLine(rs.Insert(2));
            Console.WriteLine(rs.GetRandom());
        }

        // 算法
        public class RandomizedSet
        {
            private HashSet<int> set;

            public RandomizedSet()
            {
                set = new HashSet<int>();
            }

            public bool Insert(int val)
            {
                return set.Add(val);
            }

            public bool Remove(int val)
            {
                return set.Remove(val);
            }

            public int GetRandom()
            {
                var index = new Random().Next(0, set.Count);
                return set.ElementAt(index);
            }
        }
    }
}
